//********************************
//REMEMBER 1[ONE] BASED INDEXING//
//********************************
template<class T>
    class BIT {
        private:
        int MAX_BIT;
        T *Tree;
        public:
        BIT ( int size ) {
            this->MAX_BIT = size;
            Tree = new T[this->MAX_BIT+1];
            fill ( Tree,Tree+size+1,0 );
        }
        ~BIT() {
            delete[] Tree;
        }
        inline void Update ( int idx,T delta ) {
            if ( idx<=0 ) return ;

            while ( idx<MAX_BIT ) {
                Tree[idx]+=delta;
                idx+= ( idx & -idx );
            }
        }
        inline T Query ( int idx ) {
            if ( idx<=0 ) return 0;

            T ret=0;
            while ( idx>0 ) {
                ret+=Tree[idx];
                idx-= ( idx & -idx );
            }
            return ret;
        }
    };
// kate: indent-mode cstyle; indent-width 4; replace-tabs on; 
